#include "StdAfx.h"
#include "SimpleBinaryTree.h"

//===========================================================================
// Amazon Interview
//===========================================================================
// http://www.careercup.com/page?pid=amazon-interview-questions&job=software-engineer-developer-interview-questions&topic=c-plus-plus-interview-questions

namespace quiz
{
/*
    http://www.careercup.com/question?id=16907667
    1. What is difference between override and overload 
        Override is replacing a method in a subclass with the same signature
        as a virtual method in the parent class. When called it invokes the
        subclass's version of the method instead of the parent class.
        Overload is when you modify the method signature but keep the name to
        support variants of the same procedure, its a form of parametric
        polymorphism.
    2. abstract. when will u use abstract 
        Abstract is a partially implemented class that is meant for derivation.
        It provides base functionality but leaves key implementation details to
        the user of the class. It is typically used in template-method patterns
        where the core algorithm does not change but the details of how to get
        the data are context sensitive. 
    3. what is an interface
        An interface is a completely unimplemented class that serves as a
        contract for how this abstract type will communicate with other objects.
        It provides a set of methods with signatures determining what calls
        this type supports. 
    4. what is difference betwwen array and link list
        An array is a block of memory with fast random-access times due to its
        mechanic for traversing the array (offsetting a pointer from the first
        element in the array). A linked list is a set of pairs where one element
        of the pair is a piece of data and the other is either a null link or a
        link to the next pair. Linked lists do not provide a good way of randomly
        accessing elements but they excel at insertions and deletions from any
        point in the list. 
    5. what is a tree
        A tree is an abstract data type that contains elements. It has properties
        that make it desirable for scenarios where you want to look up data quickly
        but only if certain properties are maintained. Properties are: the tree
        must be balanced, all nodes must be ordered such that every subtree to the
        left is less than or equal to the root. All nodes to the right of the root
        must be greater than the root.
    6. what is a map\dictionary
        A map or a dictionary is a data structure that connects arbitrary pieces of
        data together via a fast lookup mechanism. They are typically implemented
        with hash-tables but sometimes a balanced binary search tree like Red Black
        Trees or AVL Trees are used. 
    7. Explain (orally) how would you implement a dictionary via a tree
        Implement an AVL tree and make sure that its keys and values can support any
        type, if its a dynamically typed language then no problem just implement the
        logic behind rotations, insertions, deletions, etc. If its a statically
        typed language with a meta-programming mechanism then use that to generate
        AVL[Int,String] AVL[String, Int] etc...
*/

    // http://www.careercup.com/question?id=15069916
    /*  Given a String "abcxrrxabcrr" 
        Find the first repeated string with minimum 3 character? 
            Answer is "abc" min 3 characters.
    */
    const char * FindFirstRepeat(
        const char *       pattern,
              unsigned int count
    ) {
        if (!pattern || !*pattern)
            return NULL;

        unsigned len  = std::strlen(pattern);
        unsigned loop = len > count * 2
                      ? len - count
                      : 0;

        for (unsigned i = 0; i < loop; ++i)
            for (unsigned j = j + count; j < loop; ++j)
                if (!strncmp(&pattern[i], &pattern[j], count))
                    return &pattern[i];

        return NULL;
    }

    // http://www.careercup.com/question?id=15066927
    /*  Time Complexity of array(both sorted and unsorted) and doubly linked
        list(both sorted and unsorted)?
    
        Operation	                Array	ArrayList	Singly Linked List
        Read (any where)	        O(1)	O(1)	    O(n)
        Add/Remove at end	        O(1)	O(1)	    O(n)
        Add/Remove in the interior	O(n)	O(n)	    O(n)
        Resize	                    O(n)	N/A	        N/A
        Find By position	        O(1)	O(1)	    O(n)
        Find By target (value)	    O(n)	O(n)	    O(n)
    */


    // http://www.careercup.com/question?id=15068896
    /*  What is the difference between heap and priority queue? 
        What is its time complexity?

        * Heap
        A heap is a complete binary tree that is either:
            * empty, or
            * consists of a root and two subtrees, such that
                - both subtrees are heaps, and
                - the root contains a search key
                  that is >= the search key of each of its children.

        * priority queue
        A priority queue is an ADT in which items are ordered by a priority value.
        The item with the highest priority is always the next to be removed from the queue.
        ( Highest Priority In, First Out: HPIFO )
        Supported operations include :
            * Create an empty priority queue
            * Destroy a priority queue
            * Determine whether a priority queue is empty
            * Insert a new item into a priority queue
            * Retrieve, and then delete from the priority queue the item with the highest priority value

        * priority queue
        A priority queue is a queue which the elements are dequeued in priority
        order. They are a mutable data abstraction. Most importanlty, things can
        come out first even if they were added after. There is no really "fast"
        way of finding if an element is in the queue. It is a datastructure that
        is usefull to use where time matters, so something like a seating chart,
        we don't want people waiting for a long time, so they have a higher priority.

        Complexities are as follows: 
            insert      : O(log n) because an element must be inserted according
                          to the priority, which can be thought of as the "key". 
            extract_min : O(log n) because red-black tree deletion also requires
                          moving throughout the tree. 

        * binary heap
        A Binary Heap is a special kind of tree. It satifies two things: 
        1) The priorities of the children are at least as large as the priority of
           the parent. By this implication, the node at the top as the minimum
           priority. 
        2) The different paths from root to leaf differ in height by at most one.
           At the bottom of the tree there can be some missing nodes, but these are
           to the right of all the leaves that are present. This isn't always true
           in a priority queue. 

        You can find the min element in O(1) time. Extracting it while maintaing the
        heap itself will take O(lg n) time, inserting will take the same amount as well.
        Overall the sorting is faster in a Queue, as tehy should be sorted, but that
        isn't always the case in the heap.
    */

    // http://www.careercup.com/question?id=14781667
    /*  Write code for Queue operations add an element to queue and delete an element
        from queue. Time complexity should be O(1). Queue should be handled using an Array.
    */
    class Queue
    {
        public :

            Queue(
                unsigned int size = 0
            )   : m_size(  0    )
                , m_count( 0    )
                , m_pos(   0    )
                , m_data(  NULL )
            {
                this->Initialize( size );
            }

            virtual ~Queue( void ) {
                this->CleanUp();
            }

            void CleanUp( void ) {
                if( this->m_data ) {
                    delete [] this->m_data;
                    this->m_data = NULL;
                    
                    this->m_count = 0;
                    this->m_size  = 0;
                    this->m_pos   = 0;
                }
            }

            void Initialize(
                unsigned int size
            ) {
                this->CleanUp();
                if( !size )
                    return;

                this->m_size  = size;
                this->m_count = 0;
                this->m_pos   = 0;
                this->m_data  = new unsigned int[ this->m_size ];
            }
            
            bool GetNextIndex(
                unsigned int & index
            ) {
                if( !( this->m_count + 1 < this->m_size ) )
                    return false;

                index = this->m_pos + this->m_count;
                if( !( index < this->m_size ) )
                    index -= this->m_size;
                
                return true;
            }
            
            bool Push(
                unsigned int val
            ) {
                unsigned int index = 0;
                if( !this->GetNextIndex( index ) )
                    return false;

                this->m_data[ index ] = val;
                this->m_count++;
                
                return true;
            }

            bool Pop(
                unsigned int & val
            ) {
                if( !this->m_count )
                    return false;

                val = this->m_data[ this->m_pos ];
                
                this->m_count--;
                if( 0 == this->m_count )
                    this->m_pos = 0;
                else {
                    this->m_pos++;
                    if( !( this->m_pos < this->m_size ) )
                        this->m_pos = 0;
                }
                
                return true;
            }

            unsigned int GetCount( void ) {
                return this->m_count;
            }

        private :

            unsigned int m_pos;
            unsigned int m_count;
            unsigned int m_size;

            unsigned int * m_data;
    };

    // http://www.careercup.com/question?id=13243679
    /*  while reading a binary file with over 1 billion unsigned integers,
        how can you optimize the following code to make it perform better? 

        int  i   = 0; 
        long sum = 0; 

        std::ifstream file(
            "binary.dat",
            std::ios::in | std::ios::binary
        );

        if( file.is_open() ) 
        { 
            while( !file.eof() ) { 
                file.read(
                    reinterpret_cast< char * >( &i ),
                    sizeof( unsigned int )
                );

                sum += i; 
                i    = 0; 
            } 
        }

        file.close();
    */
    //  The optimization is to reduce the number of sys calls and read a disk
    //  block each time. Another possibility of optimization is to use
    //  multi-threading to separate the work of reading data and computing the sum.
    void ReadBigBinaryFile( void )
    {
        const unsigned int size = 4096;

        char buffer[ size ];
        long sum = 0;

        std::ifstream file(
            "binary.gif",
            std::ios::in | std::ios::binary
        );
        if( file.is_open() ) {
            while( !file.eof() )
            {
                file.read(
                    buffer,
                    sizeof( buffer ) / sizeof( char )
                );
                
                std::streamsize count = file.gcount();
                for( std::streamsize i = 0; i < count; i++ )
                    sum += static_cast< unsigned int >( buffer[ i ] );
            }

            file.close();
        }
    }

    // http://www.careercup.com/question?id=1734890
    /*  diff between pointer and reference
            - A reference must be initialized when it is created
              but pointers can be initialized at any time. 
            - Once a reference is initialized to an object,
              it cannot be changed to refer to another object
              but pointers can be pointed to another object at any time.
            - references cannot be NULL but pointers can.
            - Fundamentally reference can be taken as const pointer.
              And it is auto de-referenced.
        
    */

    // http://www.careercup.com/question?id=1736885
    /*  Height of a BInary tree.
    */

    unsigned GetNodeHeight (
        Node * node
    ) {
        if (!node)
            return 0;

        return max(
            GetNodeHeight(node->left),
            GetNodeHeight(node->right)
        ) + 1;
    }

    // http://www.careercup.com/question?id=183738
    /*  What is hard copy and shallow copy?
            - HardCopy is copying the values from one structure to another.
              If there are pointers in the structure, then the second
              structure also points to the same pointer location as in the first one.
            - Shallow copy is copying bit by bit, If there are pointers in
              the structure to be copied,then a new memory location is created
              and data is copied to that location.
    */

    // http://www.careercup.com/question?id=163738
    /*  What is the difference between using Assignment operator and Copy Constructor?
            - Assignment operator is used for Shallow Copy by overloading assignment operator. 
              Copy Constructor is used for Deep Copy
            - They are the same... In the sense both of them perform a shallow copy
              by default. You can override the default copy constructor or overload
              the assignment operator for a deep copy.
    */

    // http://www.careercup.com/question?id=3237669
    /*  Discuss object oriented features of C++.
            Polymorphism
                - Method overloading and overriding.
                - polymorphism is ability to use operatore and function in different ways in c++. 
                  there are two types,operatore overloading and function overloading.
                  in operatore overloading a single operatore + behave different in diffrenet context such as integer,float or string. 
                  In function overloading we use one funtion name with different number of parameter.
            Inheritence
            Encapsulation
    */

    // Phone Interview
    // http://www.careercup.com/question?id=15813742
    /*  find the next greatest number that can be form by same digit of the given number .. 
            sample test case
            input   4765 
            output  5467
    */
    bool GetNextGreatestNumber(
        int   number,
        int & result
    ) {
        std::vector< int > digits;
        while( number > 0 ) {
            digits.push_back( number % 10 );
            number /= 10;
        }
        unsigned int size = digits.size();
        if( size < 2 )
            return false;

        unsigned int pos = 1;
        for( unsigned int i = 0; pos < size; i++, pos++ )
            if( digits[ pos ] < digits[ i ] )
                break;
        if( pos == size )
            return false;

        for( unsigned int i = 0; i < pos; i++ )
            if( digits[ i ] > digits[ pos ] ) {
                std::swap( digits[ i ], digits[ pos ] );
                std::reverse( digits.begin(), digits.begin() + pos );
                break;
            }

        result = 0;
        std::vector< int >::reverse_iterator it = digits.rbegin();
        for( ; it != digits.rend(); it++ ) {
            result *= 10;
            result += *it;
        }

        return true;
    }

    // Phone Interview
    // http://www.careercup.com/question?id=17261664
    /*  You have unique ASCII characters. How you can sort them ? 
        Run time complexity of approach ?
    */
    void SortUniqueAsciiCharacterSet(
        char *       letters,
        unsigned int size
    ) {
        bool exist[ 256 ] = { false, };
        for( unsigned int i = 0; i < size; i++ )
            exist[ letters[ i ] ] = true;

        unsigned int index = 0;
        for( unsigned int i = 0; i < 256; i++ )
            if( exist[ i ] ) {
                letters[ index ] = i;
                index++;
            }
    }

    // Phone Interview
    // http://www.careercup.com/question?id=17164662
    /*  There are different buildings in one environment, each with machines
        that can handle one request at a time. How would you design the request
        handling so that there is no single fail-point and is scalable. 
        Hint: It is ok if a request is sent to a machine that is already servicing
        another request. We can handle requests that come back from a machine. But
        he did not want a lock on a single file that contained the data of empty machines 
        
        Follow up question was, lets say BLDG-A has 250 free machines, BLDG-B has 500
        free machines, BLDG-C has 100 free machines and BLDG-D has 0.
        How would you assign requests? What if you had 850 requests at the same time?
        Why would you assign what you did?
    */
    
    class RequestHandler
    {
    public :

        struct Building {        
            unsigned int id;
            unsigned int machines;
            unsigned int availables;

            Building(
                unsigned int machines = 0
            )   : machines(   machines )
                , availables( machines )
            {
                static unsigned int id = 0;
                this->id = id++;
            }

            Building(
                const Building & building
            )   : machines(   building.machines   )
                , availables( building.availables )
            {}

            float WorkingRate( void ) const {
                return static_cast< float >( this->availables )
                     / static_cast< float >( this->machines   );
            }
        };        
        
        RequestHandler( void ) {}
        
        ~RequestHandler( void ) {
            this->Cleanup();
        }

        void Cleanup( void ) {
            Buildings::iterator it  = this->m_buildings.begin();
            Buildings::iterator end = this->m_buildings.end();
            for( ; it != end; it++ ) {
                Building * building = *it;
                delete building;
            }
            this->m_buildings.clear();
        }

        void AddBuilding(
            unsigned int machines
        ) {
            this->m_buildings.push_back(
                new Building( machines )
            );
        }

        bool Request( void ) {
            Building * building = this->GetTopAvailableBuilding();
            if( !building )
                return false;

            if( !building->availables )
                return false;

            building->availables--;
            return true;
        }

    private :

        typedef std::deque< Building * > Buildings;

        Buildings m_buildings;

        Building * GetTopAvailableBuilding( void ) {
            if( !this->m_buildings.size() )
                return NULL;
            
            Buildings::iterator top = this->m_buildings.begin();
            Buildings::iterator it  = top + 1;
            Buildings::iterator end = this->m_buildings.end();
            for( ; it != end; it++ ) {
                if( ( *top )->WorkingRate() < ( *it )->WorkingRate() )
                    top = it;
            }

            return *top;
        }

    };

    // Phone Interview
    // http://www.careercup.com/question?id=16838681
    /*  Write an algorithm that will take two dates and tell you if they are
        more than a month apart, less than a month apart or exactly a month apart.
    
        Q : month apart means 30 days? In this what is the requirements for Feb like months?
                27Feb to 28 March are exactly one month apart.
        Q : What about Leap year issue?
    */

    bool IsLeapYear(
        unsigned int year
    ) {
        if(     ( 0 == year % 4 )
            && !( 0 == year % 100 ) )
		    return true;
			
        if( 0 == year % 400 )
            return true;
			
        return false;
    }

    // http://www.careercup.com/question?id=17024693
    /*  Given a set of array of size n, return all possible subset of size k. 
        example: if arr = { 1,2,3,4,5,6} , k=2; 
        return result is: {1,2};{1,3};{1,4};{2,3};{2,4};{3,4} 
        or a single array {1,2,1,3,1,4,2,3,2,4,3,4}
    */

    void GenerateSubSet(
        const int          array[],
              unsigned int size,
              unsigned int index,
              unsigned int count,
              std::vector< int > & prefix,
              std::vector< int > & result
    ) {
        if( !count ) {
            auto it  = prefix.begin();
            auto end = prefix.end();
            for( ; it != end; it++ )
                result.push_back( *it );
            
            return;
        }

        for( unsigned int i = index; i < size; i++ ) {
            prefix.push_back( array[ i ] );
            GenerateSubSet(
                array,
                size,
                i + 1,
                count - 1,
                prefix,
                result
            );

            prefix.pop_back();
        }
    }

    void GenerateSubSet(
        const int                  array[],
              unsigned int         size,
              unsigned int         count,
              std::vector< int > & result
    ) {
        if( !size || !( size > count ) )
            return;

        std::vector< int > prefix;
        GenerateSubSet(
            array,
            size,
            0,
            count,
            prefix,
            result
        );
    }
    
    // http://www.careercup.com/question?id=16835662
    /*  Given an array find the next greatest element to the right of it.
        [ 4, 5, 2, 25 ] Element NextGreatestElement
             4 -->  5
             5 --> 25
             2 --> 25
            25 --> -1
        I gave o( n^2 ), but was asked to solve in o(n)..You can take extra space...
    */
    bool GetNextGreatestNumber(
        const unsigned int array[],
              unsigned int size
    ) {
        if( !size )
            return false;

        vector< unsigned int > result;
        if( size < 2 )
            result.push_back( -1 );
        else {
            for( unsigned int i = 0; i < size; i++ ) {
                unsigned int next = array[ i ];
                for( unsigned int j = i + 1; j < size; j++ )
                    if( array[ j ] > array[ i ] )
                        next = next == array[ i ]
                             ? array[ j ]
                             : min( array[ j ], next );

                result.push_back( next == array[ i ] ? -1 : next );
            }
        }

        /*
        std::vector< unsigned int > result;
        unsigned int index = 1;
        for( unsigned int i = 0; i < size; i++ ) {
            bool added = false;
            if( index < size )
                for( ; index < size; index++ )
                    if( array[ index ] > array[ i ] ) {
                        result.push_back( array[ index ] );
                        added = true;
                        break;
                    }
            
            if( !added )
                result.push_back( -1 );
        }
        */

        for( unsigned int i = 0; i < size; i++ )
            printf( "%2d -> %2d\r\n", array[ i ], result[ i ] );
        std::cout << std::endl;

        return true;
    }

    // http://www.careercup.com/question?id=16432668
    /*  Given binary tree find the min weighted node. ? 
        Min weighted node is one which has minimun sum,where sum = Rootnode.getdata + leftnode.data + rightnode.data. 
        implement the method to achieve the above,,,
    */

    struct NodeWeight {
        Node *       node;
        unsigned int weight;

        explicit NodeWeight(
            Node * node
        )   : node( node )
            , weight( 0 )
        {
            if( node ) {
                weight = node->data;
                if( node->left )
                    weight += node->left->data;
                if( node->right )
                    weight += node->right->data;
            }
        }

        NodeWeight(
            const NodeWeight & nw
        )   : node(   nw.node   )
            , weight( nw.weight )
        {}
    };
    
    NodeWeight FindLightestNode(
        Node * node
    ) {
        if( !node )
            return NodeWeight( NULL );

        const unsigned int size = 3;
        NodeWeight weights[ size ] = {
            NodeWeight( node ),
            FindLightestNode( node->left ),
            FindLightestNode( node->right )
        };

        NodeWeight * lightest = &weights[ 0 ];
        for( unsigned int i = 1; i < size; i++ )
            if( weights[ i ].node )
                if( lightest->weight > weights[ i ].weight )
                    lightest = &weights[ i ];

        return *lightest;
    }

    // http://www.careercup.com/question?id=16273666
    /*  What is deque ? - double ended queue 
        Which data structures would u use to implement deque ? 
        Complexities of each data structure? 
        Implement it using array such tat all the operations are O(1). 
        operations are - insert at beginning,insert at end, delete at beginning ,delete at end. 
        How would u achieve this.? 
        Write interface and code to do the above.?

        * Use doubly linked list to implement deque, straightforward and easy to understand. 
        * We can also use an array, but it will be amortized O(1) (not worst case O(1)). 
        * Treat the array like a circular array. When we run out of space,
          use the standard vector trick to double the size and copy over the elements.
    */
    
    // http://www.careercup.com/question?id=16173689
    /*  how would u implement a function tat would generate
            x object 20% of the time,
            y object 10% of the time,
            z object 70% of the time? 
        Which data structure would u use to pass this information to the function from the main?
    */
    unsigned int GenerateRandonObject( void ) {
        int n = std::rand() % 100;
        if( n < 21 ) return 1; // x
        if( n < 31 ) return 2; // y
                     return 3; // z
    }

    // http://www.careercup.com/question?id=17002667
    /*  Class and Data Structure Design for a "metric" system to determine the top song
        of a band. Two Web Service calls: 

        void play(String bandname, String songname); 
        String topSong(String bandname); 

        CONSTRAINTS: For this exercise we should constrain the design to a single server
                     and do NOT use a database, but in memory data structure. 

        SAMPLE INPUT/OUTPUT
            play("Guns N Roses", "Welcome To the Jungle"); 
            topSong("Guns N Roses") => "Welcome To the Jungle" 
            play("Guns N Roses", "Sweet Child of Mine"); 
            topSong("Guns N Roses") => "Welcome To the Jungle" 
            play("Guns N Roses", "Sweet Child of Mine"); 
            topSong("Guns N Roses") => "Sweet Child of Mine" 
        scale the architecture
    */

    struct Song
    {
        string       name;
        unsigned int played;

        Song(
            string name
        )   : name( name )
        {}

        Song(
            const Song & song
        )   : name(   song.name   )
            , played( song.played )
        {}
    };
    
    struct Band
    {
        typedef map< string, Song * > Songs;
        
        string name;
        Song * top;
        Songs  songs;

        Band(
            const char * name
        )   : name( name )
            , top(  NULL )
        {}

        ~Band( void ) {
            auto it  = this->songs.begin();
            auto end = this->songs.end();
            for( ; it != end; it++ ) {
                Song * song = it->second;
                if( song ) {
                    delete song;
                    song = NULL;
                }
            }
            this->songs.clear();
        }

        Song * findSong(
            const char * songname
        ) {
            if( !songname || !*songname )
                return NULL;

            auto it = this->songs.find( songname );
            return it == this->songs.end()
                 ? NULL
                 : it->second;
        }

        void play(
            const char * songname
        ) {
            if( !songname || !*songname )
                return;

            Song * song = this->findSong( songname );
            if( !song ) {
                song = new Song( songname );
                this->songs.insert(
                    std::pair< std::string, Song * >(
                        songname, song
                ) );
            }
            song->played++;

            if(    !this->top 
                || song->played > top->played )
                this->top = song;
        }
    };
    
    class MusicStore
    {
    public :

        MusicStore( void ) {}
        virtual ~MusicStore( void ) {}

        void play(
            const char * bandname,
            const char * songname
        ) {
            if( !songname || !*songname )
                return;
            
            Band * band = this->findBand( bandname );
            if( !band ) {
                band = new Band( bandname );
                this->m_bands.insert(
                    pair< string, Band * >(
                        bandname, band
                ) );
            }

            band->play( songname );
        }

        const char * topSong(
            const char * bandname
        ) {
            Band * band = this->findBand( bandname );
            if( !band || !band->top )
                return NULL;

            return band->top->name.c_str();
        }

    private :

        typedef map< string, Band * > Bands;
        Bands m_bands;

        Band * findBand(
            const char * bandname
        ) {
            if( !bandname || !*bandname )
                return NULL;

            auto it = this->m_bands.find( bandname );
            return it == this->m_bands.end()
                 ? NULL
                 : it->second;
        }
    };

    
    // http://www.careercup.com/question?id=15030806
    /*  A log file which has user details(user ID,timestamp) and pages visited
        in a particular day by that user. The next day -the same kind of log
        file gets generated. How do you find the probability of users who logged
        in consecutive days out of the second day - logged in users?
        
        The question is simple, but they look for the efficient data structure
        and time complexity.
    */

    // http://www.careercup.com/question?id=15037807
    /*  A soccer league has n matches with A,B,C teams with number of goals scored by each team in each match.
        If a team wins against another team ,It gets 3 points and lost team gets 0 point.
        If a tie ,both team gets 1 point. Now how do you frame the ranking of teams.
            1) All teams played n matches. 
            2) A team 1 match,B Team 2 matches, 3 team 3 matches.Like wise it goes.
        They looked for coding and data structure techniques.
    */

    enum ETEAM {
        TEAM_A = 1 << 0,
        TEAM_B = 1 << 1,
        TEAM_C = 1 << 2,
    };

    struct Score {
        ETEAM        team;
        unsigned int score;

        Score(
            ETEAM team,
            unsigned int score
        )   : team(  team  )
            , score( score )
        {}
    };
    
    struct Match {
        Score scores[ 2 ];

        unsigned int Id( void ) const {
            return scores[ 0 ].team | scores[ 1 ].team;
        }
    };
    
    class SoccerLeague
    {
    public  :

         SoccerLeague( void ) {}
        ~SoccerLeague( void ) {}

        bool AddResult(
            const Match & match
        ) {
            unsigned int id = match.Id();
            auto found = this->m_matchs.find( id );
            if( found != this->m_matchs.end() )
                return false;

            this->m_matchs.insert(
                pair< unsigned int, Match * >(
                    id,
                    new Match(
                        match
            ) ) );

            return true;
        }

    private :

        typedef map< unsigned int, Match * > Matchs;

        Matchs m_matchs;
    };




    // http://www.careercup.com/question?id=16991676
    /*  When you enter website what is the communication you see on FIDDLER. The request responses.

        A : But its not simple to say only response. You can see everything.
            attrribute/header may be xml/html, images path and a lot of things in response.
            You can also see all the name,value pairs going along with request if URL contains a FORM submit.
            A very much useful product for debugging web applications.
    */

    // http://www.careercup.com/question?id=16606667
    /*  Given a Directed graph, and a source point say S, and say C is the most distant
        node from S, you need to find the route from S to C . Suppose ,for example there
        is a path from A-> B- >C, and a path from A->B->D->C, here the most distant node
        is C with path length as 4. Also, each edge has unit length. Since the graph is
        directed , you need to implement an algo which takes care of the cycles in the
        graph. How would you implement this?

        ref : http://azza.tistory.com/124
    */

    // http://www.careercup.com/question?id=4187843
    /*  write a program/function that converts a decimal number to its Roman numeral
        representation and vice versa.
    */
    void print_D2R(char ch, int times)
    {
	    int tIndex = 0;
	    for(tIndex = 0; tIndex < times; tIndex++)
	    {
		    printf("%c",ch);
	    }
    }

    void decimal_to_roman(int num)
    {
	    int quotient = 0;
	    int remainder = 0;
	    int index = 0;
	    int temp = 0;
	
	    if(num >= 1000)
	    {
		    quotient = num/1000;
		    remainder = num%1000;
		    if(remainder == 0)
		    {
			    print_D2R('M', quotient);
		    }
		    else
		    {
			    print_D2R('M', quotient);
			    decimal_to_roman(remainder);
		    }
	    }
	    else if(num >= 500 && num < 1000)
	    {
		    if(num >= 900 && num < 1000)
		    {
			    temp = num - 900;
			    print_D2R('C', 1);
			    print_D2R('M', 1);
			    decimal_to_roman(temp);
			    temp = 0;
		    }
		    else
		    {
			    quotient = num/500;
			    remainder = num%500;
			    if(remainder == 0)
			    {
				    print_D2R('D', quotient);
			    }
			    else
			    {
				    print_D2R('D', quotient);
				    decimal_to_roman(remainder);
			    }
		    }
	    }
	    else if(num >= 100 && num < 500)
	    {
		    if(num >= 400 && num < 500)
		    {
			    temp = num - 400;
			    print_D2R('C', 1);
			    print_D2R('D', 1);
			    decimal_to_roman(temp);
			    temp = 0;
		    }
		    else
		    {
			    quotient = num/100;
			    remainder = num%100;
			    if(remainder == 0)
			    {
				    print_D2R('C', quotient);
			    }
			    else
			    {
				    print_D2R('C', quotient);
				    decimal_to_roman(remainder);
			    }
		    }
	    }
	    else if(num >= 50 && num < 100)
	    {
		    if(num >= 90 && num < 100)
		    {
			    temp = num - 90;
			    print_D2R('X', 1);
			    print_D2R('C', 1);
			    decimal_to_roman(temp);
			    temp = 0;
		    }
		    else
		    {
			    quotient = num/50;
			    remainder = num%50;
			    if(remainder == 0)
			    {
				    print_D2R('L', quotient);
			    }
			    else
			    {
			
				    print_D2R('L', quotient);
				    decimal_to_roman(remainder);
			    }
		    }
	    }
	    else if(num >= 10 && num < 50)
	    {
		    if(num >= 40 && num < 50)
		    {
			    temp = num - 40;
			    print_D2R('X', 1);
			    print_D2R('L', 1);
			    decimal_to_roman(temp);
			    temp = 0;
		    }
		    else
		    {
			    quotient = num/10;
			    remainder = num%10;
			    if(remainder == 0)
			    {
				    print_D2R('X', quotient);
			    }
			    else
			    {
				    print_D2R('X', quotient);
				    decimal_to_roman(remainder);
			    }
		    }
	    }
	    else if(num < 10)
	    {
		    switch (num)
		    {
			    case 1:
				    printf("I");
				    break;
			    case 2:
				    printf("II");
				    break;
			    case 3:
				    printf("III");
				    break;
			    case 4:
				    printf("IV");
				    break;
			    case 5:
				    printf("V");
				    break;
			    case 6:
				    printf("VI");
				    break;
			    case 7:
				    printf("VII");
				    break;
			    case 8:
				    printf("VIII");
				    break;
			    case 9:
				    printf("IX");
				    break;
			    default:
				    break;
		    }
	    }
    }

    // http://www.careercup.com/question?id=245679
    /*  find the longest palindrome in a string?
    */

    bool IsPalindrome(
        const char *         str,
              unsigned int & length
    ) {
        length = std::strlen( str );
        
        const char * start = str;
        const char * end   = str + length - 1;
        while( start < end ) {
            if( *start != *end )
                return false;

            start++;
            end--;
        }

        return true;
    }

    bool IsPalindrome(
        const char * start,
        const char * end
    ) {
        if( !start || !*start ||
            !end   || !*end )
            return false;

        while( start < end ) {
            if( *start != *end )
                return false;

            start++;
            end--;
        }

        return true;
    }

    const char * FindLognestPalindrome(
        const char * str
    ) {
        if( !str || !*str )
            return NULL;
        
        const char * startOfPal = 0;  // start of palindrome.
        const char * endOfPal = 0;    // end of palindrome.
        int          maxLenOfPal = 0; // len of palindrome.

        unsigned int lengh = std::strlen( str );
        for (unsigned int i = 0; i < lengh; i++)
        {
            for (unsigned int j = lengh-1; j > i; j--)
            {
                const char * start = str + i;
                const char * end = str + j;

                if (IsPalindrome(start, end))
                {
                    if ((end - start + 1) > maxLenOfPal)
                    {
                        startOfPal = start;
                        endOfPal = end;
                        maxLenOfPal = end - start + 1;
                    }
                }
            }        
        }

        return startOfPal;
    }

    // http://www.careercup.com/question?id=17722662
    /*  Code to create a file system.... Have classes like directory, file and all 
        please write the full code
    */

    enum EFileProperty {
        EFP_HIDDEN    = 1 << 0,
        EFP_READONLEY = 1 << 1,
    };

    enum EFileType {
        EFT_FILE,
        EFT_DIRECTORY,
    };

    class User
    {
    public :

         User( void );
        ~User( void );
    private :
    };
    
    class File
    {
    public :

         File( void );
        ~File( void );

    private:

        size_t      m_size;
        time_t      m_lastUpdate;
        time_t      m_created;
        std::string m_path;
        User        m_owner;
        EFileType   m_type;
    };

    // http://www.careercup.com/question?id=17368679
    /*  In a BST, I want to replace all nodes with value which is the sum of all the nodes
        which are greater than equal to the current node. 
            5 
            2 10 

            Output --> 
            15 
            17 10
    */

    void TreeToList(
        Node *                   node,
        vector< unsigned int > & list
    ) {
        if( !node )
            return;

        list.push_back( node->data );
        TreeToList( node->left,  list );
        TreeToList( node->right, list );
    }
    
    void ReplaceAllNodes(
        Node *                   node,
        vector< unsigned int > & list
    ) {
        if( !node )
            return;

        auto it  = list.begin();
        auto end = list.end();
        for( ; it != end; it++ )
            if( *it >= node->data )
                break;
        for( ; it != end; it++ )
            node->data += *it;

        ReplaceAllNodes( node->left,  list );
        ReplaceAllNodes( node->right, list );
    }
    
    void ReplaceAllNodes(
        Node * root
    ) {
        if( !root )
            return;
        
        std::vector< unsigned int > list;
        TreeToList( root, list );
        std::sort( list.begin(), list.end() );

        ReplaceAllNodes(
            root,
            list
        );
    }

    // http://www.careercup.com/question?id=17368678
    /*  You are given a BST, and min, max elements. Your task is to trim this BST so
        that it contains the elements between the min and the max elements. 
        For example, given the mix and max elements [5, 13] and the tree below,
        you would return the output below.
            8
                       3                  10   
                   1       6                  14
                        4    7             13
            output should be :--->


            8
                            6           10
                               7           13
    */

    Node * TrimBST(
        Node *       node,
        unsigned int max,
        unsigned int min
    ) {
        if( !node )
            return NULL;

        node->left  = TrimBST( node->left,  max, min );
        node->right = TrimBST( node->right, max, min );

        if( node->data < min ) {
            Node * right = node->right;
            delete node;
            node = NULL;
            return right;
        }

        if( node->data > max ) {
            Node * left = node->left;
            delete node;
            node = NULL;
            return left;
        }

        return node;
    }

    // http://www.careercup.com/question?id=17567670
    /*  Design a DS for storing browsing history.
    
        This is a very complex question that needs a detailed analysis of the requirements and typical use cases.
        Only then can we properly weigh the different possible solutions.
        Below are just some simple thoughts off the top of my head: 
        A simple idea is to keep 2 data structures.
        First I'd have a doubly-linked list-based queue sorted by date for each page access.
        Each node would have the timestamp, URL, and a pointer to the node in the queue representing the next older access of that same URL.
        The queue would be capped to both a certain size and certain time range and then I could delete entries from the back of the queue as needed. 
        Second, I would have a TreeSet sorted alphabetically by URL domain name first and then by page URL within that domain name, mapping URLs to pointers to the node in the doubly-linked list that represents the most recent access to that page. 
        That way, if someone wanted to look at when all their accesses to a specific page occurred, it could be done very quickly.
        They'd be presented with URLs in alphabetical order and they'd select the right one, a lookup would be done and they'd get the record of the most recent access, and the record of the most recent access has a pointer to the next access, etc.
        Then if they wanted to see their *entire* history of visited sites, they could view the entire queue and it would be showing them a log of things they've visited in chronological order
        The use of additional data structures is possibly desirable.
        For instance, maybe we'd store a pointer somewhere to a node that's a day old, a node that's 2 days old, etc., so certain timeslices of the history could be presented with the least amount of node traversals.
        Of course these pointers would have to be updated too, but background work is much better than having time during which the user is actively waiting for something to happen. 
        That's just if it's an in-memory structure.
        Another thought is that you need to persist this data structure.
        So maybe I'd rather use something that's more like a database (but local, without the whole remote server aspect that technologies like SQL Server have).
        If you used an indexed database table, you'd want at least an index on the date and an index on the URL.    
    
    */

    // http://www.careercup.com/question?id=17506668
    /*  how do you handle your thread, to avoid dead lock and efficient
        ( generally question )

        - when writing code, make sure no lock inside another lock. if that is unavoidable, then take the locks based on lock order.
        - Prefer to Use scope locks, so that after processing the block of shared area, thread automatically release the lock.
        - Accessing the lock from all the threads should be in sequence for a critical section. Thats how dead lock can be prevented.
    */

    // http://www.careercup.com/question?id=17466666
    /*  what is Materialized view, is any different from View.

        - Materialized view is a Cached View basically used for fast data access.
        - Materialized view is disk based and are updated periodically. 
          Views are virtual and the underlying query is executed everytime the view is accesed.
    */

    // http://www.careercup.com/question?id=17572668
    /*  Given an array of integers, write a function that retrieves unique instances of any duplicates,
        returning them in a new array - 
            [ 2, 1, 2, 4, 3, 1, 5, 1 ] = [ 2, 1 ] 
            [ 1, 1, 1, 1, 1, 1, 1, 1 ] = [ 1 ] 
        Write test cases for this function
    */

    bool GenerateDuplicatesArray(
        unsigned int             array[],
        unsigned int             size,
        vector< unsigned int > & result
    ) {
        if( 0 == size || 1 == size )
            return false;

        std::vector< unsigned int > sorted;
        for( unsigned int i = 0; i < size; i++ )
            sorted.push_back( array[ i ] );
        std::sort( sorted.begin(), sorted.end() );

        for( unsigned int i = 0; i < size; i++ ) {
            unsigned int duplicated = 0;
            for( unsigned int j = i + 1; j < size; j++ ) {
                if( sorted[ i ] != sorted[ j ] )
                    break;

                duplicated++;
            }

            if( duplicated > 0 )
                result.push_back( sorted[ i ] );

            i += duplicated;
        }

        return true;
    }

    // http://www.careercup.com/question?id=17952669
    /*  Find the 3rd closest element in a bst.
        You will be given a pointer to root and a value within the tree against which the closest has to be figured out.
        ( closeness is in terms of value, not by distance ) and then follow up qn: for finding the kth closest in a bst.
    */

    void Find3rdElement(
        Node *       node,
        unsigned int value,
        unsigned int array[]
    ) {
        if( !node )
            return;

        if( node->data > value ) {
        }
        else {
        }

        Find3rdElement( node->left,  value, array );
        Find3rdElement( node->right, value, array );
    }
    
    bool Find3rdElement(
        Node *         node,
        unsigned int   value,
        unsigned int & result
    ) {
        if( !node )
            return false;

        const unsigned int size = 1 + ( 3 * 2 );
        unsigned int array[ size ] = { 0, };
        array[ 3 ] = value;
        Find3rdElement(
            node,
            value,
            array
        );

        unsigned int min = array[ 0 ];
        unsigned int max = array[ size - 1 ];
        
        if( abs( int( value - min ) ) > abs( int( value - max ) ) )
            result = max;
        else
            result = min;
     
        return true;
    }
    
    /*
    bool Find3rdElement(
        Node *         root,
        unsigned int   value,
        unsigned int & result
    ) {
        if( !root )
            return NULL;

        std::vector< unsigned int > list;
        TreeToList( root, list );
        std::sort( list.begin(), list.end() );

        unsigned int size = list.size();
        for( unsigned int i = 0; i < size - 3; i++ )
            if( list[ i ] == value ) {
                result = list[ i + 3 ];
                return true;
            }

        return false;
    }
    */

    // http://www.careercup.com/question?id=17248670
    /*  How can you implement a Hashtable with any given data structure
        What is hash function
        How can you resolve collisions

        Hash Function :
            A hash function is any algorithm or subroutine
            that maps data sets of variable length to data sets of a fixed length.
            For example, a person's name, having a variable length, could be hashed to a single integer.
            The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.
    */

    
    
    
    // http://www.careercup.com/question?id=18078662 - Written Test
    /*  write a code to print the second largest element in a list 
        Shortest possible complexity.
    */

    bool Get2ndLargestElement(
        int          array[],
        unsigned int size,
        int &        result
    ) {
        if( size < 2 )
            return false;

        int * first  = &array[ 0 ];
        int * second = &array[ 1 ];
        if( array[ 1 ] > array[ 0 ] ) {
            second = &array[ 0 ];
            first  = &array[ 1 ];
        }

        for( unsigned int i = 1; i < size; i++ )
            if( array[ i ] > *first ) {
                second = first;
                first  = &array[ i ];
            }
            else if( array[ i ] > *second )
                second = &array[ i ];

        result = *second;
        return true;
    }

    // http://www.careercup.com/question?id=18058672
    /*  Write a class For Contacts on a device 
        Implementing Search a contact was the biggest problem I faced (because search should potentially search:
        FirstName, LastName, Address, PH#, Email etc)
    */

    struct Item {
        virtual bool Find(
            const char * data
        ) = 0;
    };
    
    struct Name : public Item {
        enum NameType {
            NT_FIRST,
            NT_MIDDLE,
            NT_LAST,

            NT_COUNT
        };

        std::string name[ NT_COUNT ];

        Name(
            const char * first,
            const char * middle,
            const char * last
        ) {
            name[ NT_FIRST  ] = first;
            name[ NT_MIDDLE ] = middle;
            name[ NT_LAST   ] = last;
        }

        virtual bool Find(
            const char * data
        ) {
            if( !data || !*data )
                return false;

            for( unsigned int i = 0; i < NT_COUNT; i++ )
                if( 0 == name[ i ].compare( data ) )
                    return true;

            return false;
        }
    };

    struct Address {
        std::string    street;
        std::string    state;
        unsigned short zip;

        Address(
            const char * street,
            const char * state,
                  unsigned short zip
        )   : street( street )
            , state(  state  )
            , zip(    zip    )
        {}
    };

    struct Contact {
        Name        name;
        Address     address;
        std::string phone;
        std::string email;


        Contact(
                  Name    name,
                  Address address,
            const char *  phone,
            const char *  email
        )   : name(    name    )
            , address( address )
            , phone(   phone   )
            , email(   email   )
        {}
    };

    class Contacts
    {
    public :

        Contacts( void ) {}
        virtual ~Contacts( void ) {}
    
    private :


    };

    // http://www.careercup.com/question?id=18064671
    /*  Write a class for a parking garage: 
            One level 
            One entry point 
            No membership or payments required 
            Handles multiple types of cars
    */

    enum CarType {
        CT_1,
        CT_2,
        /* ... */

        CT_COUNT,
    };

    class Garage
    {
    public :

        Garage(
            unsigned int availables[]
        ) {
            for( unsigned int i = 0; i < CT_COUNT; i++ )
                this->m_availables[ i ] = availables[ i ];
        }

    private :

        unsigned int m_availables[ CT_COUNT ];
    };

    // http://www.careercup.com/question?id=17877682
    /*  You are given a UNIX path with dot (current) and two dots (parent). Convert this to an absolute path 
            E.g. $/home/abc/.././def/./ghi/../. 
                 becomes $/home/ghi/
    */

    vector< string >::size_type Split(
        const string &           source,
              char               delimiter,
              vector< string > & result
    ) {
        string::size_type size = source.size();
        if( size < 2 )
            return 0;
        result.clear();
        
        string::const_iterator it    = source.begin();
        string::const_iterator end   = source.end();
        string::const_iterator index = it;
        for( ; it != end; it++ ) {
            if( *it == delimiter ) {
                string element( index, it );
                if( element.size() > 0 )
                    result.push_back( element );
                
                index = it + 1;
            }
        }
        if( index < end - 1 ) {
            string element( index, it );
            if( element.size() > 0 )
                result.push_back( element );
        }
                    
        return result.size();
    }
    
    vector< string > Split(
        const string & source,
        const string & delimiter
    ) {
        vector< string > result;
        if( delimiter.empty() ) {
            result.push_back( source );
            return result;
        }

        string::const_iterator substart = source.begin();
        while( true ) {
            string::const_iterator subend = search(
                substart,
                source.end(),
                delimiter.begin(),
                delimiter.end()
            );
            
            string element( substart, subend );
            if( !element.empty() )
                result.push_back( element );
            
            if( subend == source.end() )
                break;

            substart = subend + delimiter.size();
        }

        return result;
    }
    
    bool ConvertUnixPathToAbsolutePath(
        const char *   source,
              string & dest
    ) {
        if( !source || !*source )
            return false;

        vector< string > paths;
        vector< string >::size_type count = Split(
            string( source ),
            '/',
            paths
        );
        if( count < 1 )
            return false;

        vector< string >::iterator it  = paths.begin();
        vector< string >::iterator end = paths.end();
        vector< string > path;
        for( ; it != end; it++ ) {
            const char * element = ( *it ).c_str();
            if( !*element )
                continue;

            if( '.' == *element ) {
                if( '.' == *( element + 1 ) )
                    path.pop_back();
                
                continue;
            }

            path.push_back( element );
        }

        dest.clear();
        it  = path.begin();
        end = path.end();
        for( ; it != end; it++ ) {
            dest.append( *it );
            dest.append( "/" );
        }
        
        return true;
    }


    // http://www.careercup.com/question?id=17877683
    /*  A video streaming server is generating the following data. Find the potential customers facing buffering issues. 
        A person is said to face buffering issues when he hits the play button multiple times on the same video 
        You are given a huge file (say 1GB) that contains the following data: 
        CustomerId-TimeStamp-Event-VideoId-Videolength 
        0040 -01.00pm -Play -Video1 -02:30:00 
        Write code for this. What data structure will you use
        
        He also said, lets say all the parsing is taken care of and you are given a collection of classes that contain the above data:
        
        Class 
        {
	        CustomerId
	        TimeStamp
	        Event
	        VideoId
        }
    */

    struct CustomerId {
    };

    struct VideoId {
    };
    
    class VideoStreamingServer
    {
    public :

        enum EEvent {
            EE_PLAY,
            EE_COUNT
        };
        
        struct Data {
            CustomerId customer;
            VideoId    video;
            time_t     time;
            EEvent     event;
        };

    private :
    };

    
    // http://www.careercup.com/question?id=18064672
    /*  There is a HealthMonitor and two Servers (Primary and Secondary), all connected to one and another. 
        The HealthMonitor keeps pinging both the servers at specific time intervals and waits for their response
        for a time-out period after the request has been sent. 
        The server responds with a health status of itself and of its neighbor (meaning Primary responsds: OK; NEIGHBOR_OK) 
        Implement the server's code to send and receive responses and then take action based on response.
    */

    struct NetAddress {
        unsigned int address;
        unsigned int port;

        NetAddress(
            unsigned int address,
            unsigned int port
        )   : address( address )
            , port(    port    )
        {}

        NetAddress(
            const NetAddress & na
        )   : address( na.address )
            , port(    na.port    )
        {}
    };

    struct Packet {
        enum EProtocol {
            EP_REQUEST_HEALTH_STATUS,

            EP_COUNT,
        };

        struct Data {
            void *       data;
            unsigned int size;

            Data(
                void *       data,
                unsigned int size
            )   : data( data )
                , size( size )
            {}

            Data(
                const Data & data
            )   : data( data.data )
                , size( data.size )
            {}

            Data(
                void
            )   : data( NULL )
                , size( 0    )
            {}
        };

        Packet(
            EProtocol protocol,
            Data      data
        )   : protocol( protocol )
            , data(     data     )
        {}

        Packet(
            EProtocol protocol
        )   : protocol( protocol )
        {}

        EProtocol    protocol;
        unsigned int transactionId;
        Data         data;
    };
    
    class Neighbor
    {
    public :

        Neighbor(
            NetAddress address
        )   : m_address( address )
        {}

        Packet::Data * Request(
            const Packet &     packet,
                  unsigned int timeoutMs,
                  bool         sync = true
        );

        void Response(
            const Packet *       request,
            const Packet::Data & data
        );

        bool IsFromNeighbor(
            const Packet * packet
        );

    private :

        NetAddress m_address;
    };
    
    class Server
    {
    public :

        enum EHealthStatus {
            EHS_OK,
            EHS_NOT_OK,
        };

        Server(
            unsigned int timeoutMs,
            NetAddress   neighbor
        )   : m_timeoutMs( timeoutMs )
            , m_neighbor(  neighbor  )
        {}

        
    private :

        void Response(
            const NetAddress &      to,
                  Packet::EProtocol protocol,
            const Packet::Data &    data
        ) {
        }

        void Request(
            const NetAddress &      to,
                  Packet::EProtocol protocol
        ) {
        }
        
        void OnRead(
            const Packet * packet
        ) {
            if( !packet )
                return;

            switch( packet->protocol ) {
            case Packet::EP_REQUEST_HEALTH_STATUS :
                if( this->m_neighbor.IsFromNeighbor( packet ) )
                    this->m_neighbor.Response(
                        packet,
                        Packet::Data(
                            ( void * )( &this->m_status ),
                            sizeof( this->m_status )
                    ) );
                else {
                    Packet::Data * response = NULL;
                    while( true ) {
                        response = this->m_neighbor.Request(
                            Packet( Packet::EP_REQUEST_HEALTH_STATUS ),
                            this->m_timeoutMs,
                            true
                        );
                        if( response )
                            break;
                    }
                    
                    /* ack response */
                }

                break;
            };
        }

        Neighbor      m_neighbor;
        unsigned int  m_timeoutMs;
        EHealthStatus m_status;
    };


    // http://www.careercup.com/question?id=18062667
    /*  Implement an iterator for a Binary tree. It should have the following things: 
            1. bool HasNext()	
            2. <T> Next() 
        It should be an in-order traversal.
    */

    namespace BT
    {
        template< typename T >
        struct Node {
            Node(
                Node< T > * parent,
                T           item
            )   : parent( parent )
                , item(   item   )
                , left(   NULL   )
                , right(  NULL   )
            {}
            
            T           item;
            Node< T > * parent;
            Node< T > * left;
            Node< T > * right;
        };

        template< typename T >
        class Iterator
        {
        public  :

            Iterator(
                Node< T > * node
            )   : m_next( node )
            {}

            bool HasNext( void ) {
                return NULL != this->m_next;
            }

            T Next( void ) {
                if( !this->m_next )
                    throw;

                T item = this->m_next->item;

                if( this->m_next->left )
                    this->m_next = this->m_next->left;
                else if( this->m_next->right )
                    this->m_next = this->m_next->right;
                else {
                    Node< T > * parent = this->m_next->parent;
                    Node< T > * child  = this->m_next;
                    while( parent
                        && (   parent->right == child
                            || NULL == parent->right ) ) {
                        child  = parent;
                        parent = parent->parent;
                    }

                    this->m_next = parent
                                 ? parent->right;
                                 : NULL;
                }

                return item;
            }

        private :

            Node< T > * m_next;
        };
    };


    // http://www.careercup.com/question?id=18069668
    /*  Implement: 
            1. a search that will return all the strings that match a sub-string 
            2. an insert into this datastructure

        Class
        {
	        Insert( string str ){};
	        
            List< strings > Predictions(
                string subString
            ) {};
        };
    */

    // http://www.careercup.com/question?id=18069669
    /*  Write a class that will have following functions: 
            long CheckOut() 
            CheckIn(long) 

        Range of values is 1 to LONG_MAX 
        At any given point in time checkout should return the minimum available LONG number 
        Checkin can return the value back 
        No need to check for border conditions (e.g. check out when all values are exhausted) 
            Implement: 
                1. long checkout() 
                2. void checkIn(long input)
    */

    class Check
    {
    public :

         Check( void ) : m_val( 0 ) {}
        ~Check( void ) {}

        long CheckOut( void ) {
            if( this->m_checks.size() < 1 )
                return ++this->m_val;
            else {
                set< long >::iterator begin = this->m_checks.begin();
                long val = *begin;
                this->m_checks.erase( begin );                
                return val;
            }
        }

        void CheckIn( long val ) {
            if( val == this->m_val )
                this->m_val--;
            else
                this->m_checks.insert( val );
        }

    private :

        set< long > m_checks;
        long        m_val;
    };


    // web-service
    // http://www.careercup.com/question?id=17995666
    /*  Adding Very Large Numbers. Write clean code for it. please check all corner cases.. 
        Number can be really really large
    */

    // in-person

    // http://www.careercup.com/question?id=18839665
    /*  How would you test amazon search functionality on the home page?

        * copy/paste ads from home page search box and then compare prices
        *   - positive/negative searches and the results returned. 
            - filtering, sorting the results returned. 
            - searches in different languages (Spanish, Korean, etc.). 
    */

    // http://www.careercup.com/question?id=18892662
    /*  There are exactly N advertising boards on the highway. Now a company want to advertise
        on some of these advertising boards (each advertising board costs some money). 
        Company strategy is that, they want at least 'K' advertisement should be there among M
        consecutive advertising boards. But at the same time Company want to pay minimum for
        its advertisement. 
        Now, what is the total number of ways Company can advertise meeting its minimum cost
        strategy. Also 1 <= K <= M <= 50 and M <= N <= 10 ^ 9 
        
        As for Example :
            N = 3, M = 2, K = 1 ==> there is only one way for minimum cost, ie. 0C0 ,
            where '0' denotes No company advertisement, and 'C' denotes company advertisement board. 
            Similarly, for N = 4, M = 2, K = 1 ==> there are 3 possible ways, ie. C0C0, 0C0C, 0CC0.
    */


    // http://www.careercup.com/question?id=18788682
    /*  Given an array with different numbers and a number of C,so how to find all the
        combinations which the sum is C..like..array = { 1, 2, 3, 4 }, C = 3, , return is 2, which
        contains two combinations{ { 1, 2 }, { 3 } }.
    */

    void GernerateAllCombination(
        const vector< unsigned int > & values,
              unsigned int             index,
              vector< unsigned int > & combination,
              vector< vector< unsigned int > > &
                                       combinations
    ) {
        vector< unsigned int >::size_type size = values.size();
        if( !( index < size ) )
            return;

        vector< unsigned int >::size_type i = index;
        for( ; i < size; i++ ) {
            combination.push_back( values[ i ] );
            combinations.push_back( combination );

            GernerateAllCombination(
                values,
                i + 1,
                combination,
                combinations
            );

            combination.pop_back();
        }
    }

    void GernerateAllCombination(
        const vector< unsigned int > &           values,
              vector< vector< unsigned int > > & combinations
    ) {
        vector< unsigned int > combination;
        GernerateAllCombination(
            values,
            0,
            combination,
            combinations
        );
    }
    
    void GernerateAllCombination(
        unsigned int array[],
        unsigned int size,
        vector< vector< unsigned int > > &
                 combinations
    ) {
        vector< unsigned int > values;
        for( unsigned int i = 0; i < size; i++ )
            values.push_back( array[ i ] );
        
        GernerateAllCombination(
            values,
            combinations
        );
    }
        
    

    // http://www.careercup.com/question?id=18782681

    // http://www.careercup.com/question?id=18078662

    // http://www.careercup.com/question?id=18047673
        
    // http://www.careercup.com/question?id=18078662
};

/*
$ wc file.txt   /// this is how I run the program
lines: 47   words: 131   bytes: 925   // it should print this


wc = word count
it's a program

counts the words in a file

#include <iostream>

int main (int argc, char *argv[]) {
    if (2 > argc)
        return -1;
        
    FILE * file = fopen(argv[1]);
    if (!file)
        return -2;
        
    unsigned lines = 0;
    unsigned words = 0;
    unsigned bytes = 0;
    
    char buffer = 0;
    bool prev   = false; // means already counted word
    while (fread(buffer, 1, 1, file)) {
        ++bytes;
        
        switch (buffer) {
            case '\n':
                ++lines;
            case ' ':
            case '\t':
                if (!prev) {
                    ++words;
                    prev = true;
                }
                break;
            default:
                prev = false;
                break;
        }
        
        fseek(file, 1, SEEK_CUR);
    }
    
    fclose(file);    
    file = NULL;
    
    std::cout << "lines: " << lines
              << "words: " << words
              << "bytes: " << bytes;
    
    return 0;
}
*/